Distance graphs with maximum chromatic number

Distance graphs with maximum chromatic number

Let $D$ be a finite set of integers. The distance graph $G(D)$ has the set of integers as vertices and two vertices at distance $d ∈D$ are adjacent in $G(D)$. A conjecture of Xuding Zhu states that if the chromatic number of $G (D)$ achieves its maximum value $|D|+1$ then the graph has a clique of o...

Бүрэн тодорхойлолт

Номзүйн дэлгэрэнгүй
Үндсэн зохиолчид:	Javier Barajas, Oriol Serra
Формат:	Өгүүллэг
Хэл сонгох:	English
Хэвлэсэн:	Discrete Mathematics & Theoretical Computer Science 2005-01-01
Цуврал:	Discrete Mathematics & Theoretical Computer Science
Нөхцлүүд:	distance graphs chromatic number [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co]
Онлайн хандалт:	https://dmtcs.episciences.org/3391/pdf

Ижил төстэй зүйлс

An upper bound for the chromatic number of line graphs
-н: Andrew D. King, зэрэг
Хэвлэсэн: (2005-01-01)

(k − 2)-linear connected components in hypergraphs of rank k
-н: Florian Galliot, зэрэг
Хэвлэсэн: (2023-11-01)

On Kerov polynomials for Jack characters (extended abstract)
-н: Valentin Féray, зэрэг
Хэвлэсэн: (2013-01-01)

On the $L(p,1)$-labelling of graphs
-н: Daniel Gonçalves
Хэвлэсэн: (2005-01-01)

Staircase Macdonald polynomials and the $q$-Discriminant
-н: Adrien Boussicault, зэрэг
Хэвлэсэн: (2008-01-01)

A product formula for the TASEP on a ring
-н: Erik Aas, зэрэг
Хэвлэсэн: (2014-01-01)

Noncommutative Symmetric Hall-Littlewood Polynomials
-н: Lenny Tevlin
Хэвлэсэн: (2011-01-01)

$K_{\ell}^{-}$-factors in graphs
-н: Daniela Kühn, зэрэг
Хэвлэсэн: (2005-01-01)

Fast separation in a graph with an excluded minor
-н: Bruce Reed, зэрэг
Хэвлэсэн: (2005-01-01)

Acyclic Coloring of Graphs of Maximum Degree $\Delta$
-н: Guillaume Fertin, зэрэг
Хэвлэсэн: (2005-01-01)

Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$
-н: John Talbot
Хэвлэсэн: (2005-01-01)

Application of graph combinatorics to rational identities of type $A^\ast$
-н: Adrien Boussicault, зэрэг
Хэвлэсэн: (2009-01-01)

Packing non-returning A-paths algorithmically
-н: Gyula Pap
Хэвлэсэн: (2005-01-01)

Multigraph decomposition into multigraphs with two underlying edges
-н: Miri Priesler, зэрэг
Хэвлэсэн: (2005-01-01)

Hamiltonian Chains in Hypergraphs
-н: Gyula Y. Katona
Хэвлэсэн: (2005-01-01)

Counting Polyominoes on Twisted Cylinders
-н: Gill Barequet, зэрэг
Хэвлэсэн: (2005-01-01)

On the Minimum Number of Completely 3-Scrambling Permutations
-н: Jun Tarui
Хэвлэсэн: (2005-01-01)

Counting Shi regions with a fixed separating wall
-н: Susanna Fishel, зэрэг
Хэвлэсэн: (2011-01-01)

A Quantization of a theorem of Goulden and Jackson
-н: Matjaž Konvalinka, зэрэг
Хэвлэсэн: (2008-01-01)

Indecomposable permutations with a given number of cycles
-н: Robert Cori, зэрэг
Хэвлэсэн: (2009-01-01)

Enumeration of alternating sign matrices of even size (quasi)-invariant under a quarter-turn rotation
-н: Jean-Christophe Aval, зэрэг
Хэвлэсэн: (2009-01-01)

Noncommutative symmetric functions III : Deformations of Cauchy and convolution algebras
-н: Gérard Duchamp, зэрэг
Хэвлэсэн: (1997-01-01)

Colouring random geometric graphs
-н: Colin J. H. McDiarmid, зэрэг
Хэвлэсэн: (2005-01-01)

Relaxed Two-Coloring of Cubic Graphs
-н: Robert Berke, зэрэг
Хэвлэсэн: (2005-01-01)

A sufficient condition for bicolorable hypergraphs
-н: David Défossez
Хэвлэсэн: (2005-01-01)

Excluded subposets in the Boolean lattice
-н: Gyula O.H. Katona
Хэвлэсэн: (2005-01-01)

A Min-Max theorem about the Road Coloring Conjecture
-н: Rajneesh Hegde, зэрэг
Хэвлэсэн: (2005-01-01)

Discrepancy of Products of Hypergraphs
-н: Benjamin Doerr, зэрэг
Хэвлэсэн: (2005-01-01)

Structure of spaces of rhombus tilings in the lexicograhic case
-н: Éric Rémila
Хэвлэсэн: (2005-01-01)

Mader Tools
-н: Frank Göring
Хэвлэсэн: (2005-01-01)

Affine permutations and rational slope parking functions
-н: Eugene Gorsky, зэрэг
Хэвлэсэн: (2014-01-01)

A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants (condensed version)
-н: J. Haglund
Хэвлэсэн: (2011-01-01)

On the enumeration of column-convex permutominoes
-н: Nicholas R. Beaton, зэрэг
Хэвлэсэн: (2011-01-01)

The purity of set-systems related to Grassmann necklaces
-н: Vladimir Danilov, зэрэг
Хэвлэсэн: (2014-01-01)

Combinatorial properties of permutation tableaux
-н: Alexander Burstein, зэрэг
Хэвлэсэн: (2008-01-01)

A bijective proof of a factorization formula for Macdonald polynomials at roots of unity
-н: F. Descouens, зэрэг
Хэвлэсэн: (2008-01-01)

A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests
-н: Heesung Shin, зэрэг
Хэвлэсэн: (2009-01-01)

A bijection between shrubs and series-parallel posets
-н: Frédéric Chapoton
Хэвлэсэн: (2008-01-01)

Statistics on staircase tableaux, eulerian and mahonian statistics
-н: Sylvie Corteel, зэрэг
Хэвлэсэн: (2011-01-01)

Combinatorics of k-shapes and Genocchi numbers
-н: Florent Hivert, зэрэг
Хэвлэсэн: (2011-01-01)