Journal article
On a tiling conjecture of Komlós for 3-chromatic graphs
Discrete mathematics, v 277(01-03), pp 171-191
28 Feb 2004
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
Given two graphs G and H, an H-matching of G (or a tiling of G with H) is a subgraph of G consisting of vertex-disjoint copies of H. For an r-chromatic graph H on h vertices, we write u=u(H) for the smallest possible color-class size in any r-coloring of H. The critical chromatic number of H is the number χcr(H)=(r−1)h/(h−u). A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n-vertex graph of minimum degree at least (1−(1/χcr(H)))n, then G contains an H-matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n when H is a 3-chromatic graph.
Metrics
Details
- Title
- On a tiling conjecture of Komlós for 3-chromatic graphs
- Creators
- Ali Shokoufandeh - Drexel UniversityYi Zhao - Rutgers, The State University of New Jersey
- Publication Details
- Discrete mathematics, v 277(01-03), pp 171-191
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000188962500011
- Scopus ID
- 2-s2.0-0742320659
- Other Identifier
- 991019168209204721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics