Timeline for Properties of bipartite graphs
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2016 at 22:33 | comment | added | martin tassy | I am sincerely sorry for the approximative formulation, I am not very knowledgeable in graph theory. What I am looking for is for a different characterization of the property 2 (I need to check if some particular Cayley graph has it). Clearly chordal bipartite or having minimal cycles of length 4 does not work since the discretization of $S^2$ into a grid does not have property 2. I was hoping to find a reference in the literature. | |
| Feb 6, 2016 at 22:27 | comment | added | martin tassy | I sincerely appreciate your answer, thank you very much. | |
| Feb 6, 2016 at 22:26 | comment | added | Fedor Petrov | @martintassy What do you mean by "broken into cycle of length 4"? Usually chordal graph is about chords, it is natural to think the same for chordal bipartite. | |
| Feb 6, 2016 at 22:26 | comment | added | David Eppstein | Still no. Remove one vertex from a cube. Then the three neighbors of the removed vertex have no median, but the three remaining 4-cycles form a cycle basis (the remaining 6-cycle can be "broken into" three 4-cycles, in the same sense that the outer 8-cycle of a 3x3 grid can be broken into four 4-cycles. | |
| Feb 6, 2016 at 22:23 | comment | added | martin tassy | Sorry I think the property I am looking for is that every minimal cycle has length 4, that is every cycle of length strictly greater than 4 can be broken into cycle of length 4 ( which is the case of the 3x3 grid). I am not very knowledgeable in graph theory so I thought this was the definition of chordal bipartite. | |
| Feb 6, 2016 at 22:17 | history | answered | David Eppstein | CC BY-SA 3.0 |