| Title: | Linear colorings of graphs |
|---|
| Authors: | ID Hilaire, Claire (Author)
ID Krnc, Matjaž (Author)
ID Milanič, Martin (Author)
ID Raymond, Jean-Florent (Author) |
|---|
| Files: |  https://www.sciencedirect.com/science/article/pii/S0195669826000429?via%3Dihub
https://arxiv.org/abs/2505.02768
 RAZ_Hilaire_Claire_2026.pdf (713,67 KB, This file will be accessible after 23.03.2028)
MD5: E9BF7B15C8170FC983D59D9B67A07B04
|
|---|
| Language: | English |
|---|
| Work type: | Unknown |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FAMNIT - Faculty of Mathematics, Science and Information Technologies
|
|---|
| Abstract: | Motivated by algorithmic applications, Kun, O’Brien, Pilipczuk, and Sullivan introduced the parameter linear chromatic number as a relaxation of treedepth and proved that the two parameters are polynomially related. They conjectured that treedepth could be bounded from above by twice the linear chromatic number. In this paper we investigate the properties of linear chromatic number and provide improved bounds in several graph classes. |
|---|
| Keywords: | linear coloring, central coloring, treedepth |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.05.2026 |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | str. 1-22 |
|---|
| Numbering: | Vol. 135, [article no.] ǂ104374 |
|---|
| PID: | 20.500.12556/RUP-22852  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0195-6698 |
|---|
| DOI: | 10.1016/j.ejc.2026.104374 |
|---|
| COBISS.SI-ID: | 272926979 |
|---|
| Publication date in RUP: | 25.03.2026 |
|---|
| Views: | 97 |
|---|
| Downloads: | 3 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
