Timeline for List chromatic index of a particular graph
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 30, 2020 at 19:11 | vote | accept | vidyarthi | ||
| Jul 30, 2020 at 18:55 | comment | added | Gregory J. Puleo | I suspect there would still be far too many previously-colored adjacent edges for the late edges within $A$. Note that the last edge considered within $A$ will have $2p-1$ previously-colored adjacent edges just within $A$, and therefore couldn't afford to be incident to any edges going to $B$. I think the only way to relax the hypothesis you stated in the question and have this proof still go through is to allow vertex $a_i$ to have degree at most $i-1$ in $B$, rather than degree exactly $i-1$ (and likewise for $B$-vertices). | |
| Jul 30, 2020 at 18:52 | comment | added | vidyarthi | ok, let us limit the degree of the bipartite graph to a maximum of $p$, then I think it should be possible,right? | |
| Jul 30, 2020 at 18:46 | comment | added | Gregory J. Puleo | The degree constraint is essential here for arguing that each edge has few enough previously-colored adjacent edges going to $B$. In the extreme case where the bipartite graph was $K_{p+1, p+1}$, the whole graph would just be $K_{2p+2}$, and then no matter how you slice it the last edge you consider will have $2(2p+1) - 1 = 4p+1$ previously-colored adjacent edges. | |
| Jul 30, 2020 at 18:03 | comment | added | vidyarthi | by the way, would replacing the bipartite graph with arbitrary bipartite graph have any effect (I dont think so)? If so, then I think we could extend this method to prove edge chromatic choosability for all graphs with maximum degree$\ge\frac{n}{2}$, whre $n$ is the order of the graph | |
| Jul 30, 2020 at 18:00 | comment | added | vidyarthi | great! but I think first coloring the edges of $A$ (or $B$) and then the edges of the bipartite graph and lastly $B$ (or $A$) would also work. But, for this, I would use the paer refereed and the Galvin' stheorem. | |
| Jul 29, 2020 at 22:22 | history | edited | Gregory J. Puleo | CC BY-SA 4.0 |
added 4 characters in body
|
| Jul 29, 2020 at 22:14 | history | edited | Gregory J. Puleo | CC BY-SA 4.0 |
added 5 characters in body
|
| Jul 29, 2020 at 22:08 | history | undeleted | Gregory J. Puleo | ||
| Jul 29, 2020 at 22:08 | history | edited | Gregory J. Puleo | CC BY-SA 4.0 |
added 270 characters in body
|
| Jul 29, 2020 at 21:43 | history | edited | Gregory J. Puleo | CC BY-SA 4.0 |
deleted 37 characters in body
|
| Jul 29, 2020 at 21:31 | history | deleted | Gregory J. Puleo | via Vote | |
| Jul 29, 2020 at 21:31 | history | undeleted | Gregory J. Puleo | ||
| Jul 29, 2020 at 21:30 | history | deleted | Gregory J. Puleo | via Vote | |
| Jul 29, 2020 at 21:29 | history | answered | Gregory J. Puleo | CC BY-SA 4.0 |