|
|
|
|
counterexamples to a conjecture on matching kneser graphs
|
|
|
|
|
|
|
|
نویسنده
|
iradmusa moharram n
|
|
منبع
|
transactions on combinatorics - 2023 - دوره : 12 - شماره : 3 - صفحه:172 -173
|
|
چکیده
|
Let g be a graph and r ∈ n. the matching kneser graph kg(g, rk2) is a graph whose vertex set is the set of r-matchings in g and two vertices are adjacent if their corresponding matchings are edge-disjoint. in [m. alishahi and h. hajiabolhassan, on the chromatic number of matching kneser graphs, combin. probab. and comput., 29, no. 1 (2020), 1–21] it was conjectured that for any connected graph g and positive integer r ≥ 2, the chromatic number of kg(g, rk2) is equal to |e(g)| − ex(g, rk2), where ex(g, rk2) denotes the largest number of edges in g avoiding a matching of size r. in this note, we show that the conjecture is not true for snarks.
|
|
کلیدواژه
|
matching kneser graph ,snarks ,chromatic number
|
|
آدرس
|
shahid beheshti university, department of mathematical sciences, iran
|
|
پست الکترونیکی
|
m_iradmusa@sbu.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|