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...

Bibliografske podrobnosti
Main Authors:	Javier Barajas, Oriol Serra
Format:	Article
Jezik:	English
Izdano:	Discrete Mathematics & Theoretical Computer Science 2005-01-01
Serija:	Discrete Mathematics & Theoretical Computer Science
Teme:	distance graphs chromatic number [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co]
Online dostop:	https://dmtcs.episciences.org/3391/pdf

Podobne knjige/članki

An upper bound for the chromatic number of line graphs
od: Andrew D. King, et al.
Izdano: (2005-01-01)

(k − 2)-linear connected components in hypergraphs of rank k
od: Florian Galliot, et al.
Izdano: (2023-11-01)

On Kerov polynomials for Jack characters (extended abstract)
od: Valentin Féray, et al.
Izdano: (2013-01-01)

On the $L(p,1)$-labelling of graphs
od: Daniel Gonçalves
Izdano: (2005-01-01)

Staircase Macdonald polynomials and the $q$-Discriminant
od: Adrien Boussicault, et al.
Izdano: (2008-01-01)

A product formula for the TASEP on a ring
od: Erik Aas, et al.
Izdano: (2014-01-01)

Noncommutative Symmetric Hall-Littlewood Polynomials
od: Lenny Tevlin
Izdano: (2011-01-01)

$K_{\ell}^{-}$-factors in graphs
od: Daniela Kühn, et al.
Izdano: (2005-01-01)

Fast separation in a graph with an excluded minor
od: Bruce Reed, et al.
Izdano: (2005-01-01)

Acyclic Coloring of Graphs of Maximum Degree $\Delta$
od: Guillaume Fertin, et al.
Izdano: (2005-01-01)

Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$
od: John Talbot
Izdano: (2005-01-01)

Application of graph combinatorics to rational identities of type $A^\ast$
od: Adrien Boussicault, et al.
Izdano: (2009-01-01)

Packing non-returning A-paths algorithmically
od: Gyula Pap
Izdano: (2005-01-01)

Multigraph decomposition into multigraphs with two underlying edges
od: Miri Priesler, et al.
Izdano: (2005-01-01)

Hamiltonian Chains in Hypergraphs
od: Gyula Y. Katona
Izdano: (2005-01-01)

Counting Polyominoes on Twisted Cylinders
od: Gill Barequet, et al.
Izdano: (2005-01-01)

On the Minimum Number of Completely 3-Scrambling Permutations
od: Jun Tarui
Izdano: (2005-01-01)

Counting Shi regions with a fixed separating wall
od: Susanna Fishel, et al.
Izdano: (2011-01-01)

A Quantization of a theorem of Goulden and Jackson
od: Matjaž Konvalinka, et al.
Izdano: (2008-01-01)

Indecomposable permutations with a given number of cycles
od: Robert Cori, et al.
Izdano: (2009-01-01)

Enumeration of alternating sign matrices of even size (quasi)-invariant under a quarter-turn rotation
od: Jean-Christophe Aval, et al.
Izdano: (2009-01-01)

Noncommutative symmetric functions III : Deformations of Cauchy and convolution algebras
od: Gérard Duchamp, et al.
Izdano: (1997-01-01)

Colouring random geometric graphs
od: Colin J. H. McDiarmid, et al.
Izdano: (2005-01-01)

Relaxed Two-Coloring of Cubic Graphs
od: Robert Berke, et al.
Izdano: (2005-01-01)

A sufficient condition for bicolorable hypergraphs
od: David Défossez
Izdano: (2005-01-01)

Excluded subposets in the Boolean lattice
od: Gyula O.H. Katona
Izdano: (2005-01-01)

A Min-Max theorem about the Road Coloring Conjecture
od: Rajneesh Hegde, et al.
Izdano: (2005-01-01)

Discrepancy of Products of Hypergraphs
od: Benjamin Doerr, et al.
Izdano: (2005-01-01)

Structure of spaces of rhombus tilings in the lexicograhic case
od: Éric Rémila
Izdano: (2005-01-01)

Mader Tools
od: Frank Göring
Izdano: (2005-01-01)

Affine permutations and rational slope parking functions
od: Eugene Gorsky, et al.
Izdano: (2014-01-01)

A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants (condensed version)
od: J. Haglund
Izdano: (2011-01-01)

On the enumeration of column-convex permutominoes
od: Nicholas R. Beaton, et al.
Izdano: (2011-01-01)

The purity of set-systems related to Grassmann necklaces
od: Vladimir Danilov, et al.
Izdano: (2014-01-01)

Combinatorial properties of permutation tableaux
od: Alexander Burstein, et al.
Izdano: (2008-01-01)

A bijective proof of a factorization formula for Macdonald polynomials at roots of unity
od: F. Descouens, et al.
Izdano: (2008-01-01)

A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests
od: Heesung Shin, et al.
Izdano: (2009-01-01)

A bijection between shrubs and series-parallel posets
od: Frédéric Chapoton
Izdano: (2008-01-01)

Statistics on staircase tableaux, eulerian and mahonian statistics
od: Sylvie Corteel, et al.
Izdano: (2011-01-01)

Combinatorics of k-shapes and Genocchi numbers
od: Florent Hivert, et al.
Izdano: (2011-01-01)