- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- A coloring algorithm for $4K_1$-free line graphs
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
A coloring algorithm for $4K_1$-free line graphs Maffray, Frederic
Description
When $F$ is a set of four-vertex graphs the complexity of the vertex coloring problem in the class of $F$-free graphs is known, with three exceptions: $F = \{\text{claw}, 4K_1\}$, $F = \{\text{claw}, 4K_1, \text{co-diamond}\}$, and $F = \{C_4, 4K_1\}$. We study the coloring problem for $\{\text{claw},4K_1\}$-free graphs. We solve the vertex coloring problem for a subclass of this class which contains the class of $4K_1$-free line graphs. Our result implies that the chromatic index of a graph with no matching of size four can be computed in polynomial time. Joint work with Dallas J. Fraser, Angele M. Hamel, Chinh T. Hoang (Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, Canada)
Item Metadata
| Title |
A coloring algorithm for $4K_1$-free line graphs
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2017-08-24T10:31
|
| Description |
When $F$ is a set of four-vertex graphs the complexity of the vertex coloring
problem in the class of $F$-free graphs is known, with three exceptions: $F =
\{\text{claw}, 4K_1\}$, $F = \{\text{claw}, 4K_1, \text{co-diamond}\}$, and $F = \{C_4, 4K_1\}$. We study the
coloring problem for $\{\text{claw},4K_1\}$-free graphs. We solve the vertex coloring
problem for a subclass of this class which contains the class of $4K_1$-free
line graphs. Our result implies that the chromatic index of a graph with no
matching of size four can be computed in polynomial time.
Joint work with Dallas J. Fraser, Angele M. Hamel, Chinh T. Hoang
(Department of Physics and Computer Science, Wilfrid
Laurier University, Waterloo, Ontario, Canada)
|
| Extent |
19 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Laboratoire G-SCOP
|
| Series | |
| Date Available |
2018-04-12
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0365554
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International